package com.practice.binarysearch;

/**
 * Given two sorted arrays A, B of size m and n respectively. Find the k-th
 * smallest element in the union of A and B. You can assume that there are no
 * duplicate elements. (G)
 * 
 * Assumption: m + n >= k
 */
public class FindKInTwoSorted {
	/*
	public int get(int[] a, int[] b, int k) {
		int lower = Math.max(0, k - b.length - 1);
		int upper = Math.min(a.length - 1, k - 1);
		int i = (lower + upper) / 2;
		return get(a, b, k, lower, i, upper);
	}

	private int get(int[] a, int[] b, int k, int lower, int i, int upper) {
		int j = k - i - 2;
		if (j < 0)
			return Math.min(a[i], b[0]);

		if (a[i] == b[j]) {
			return a[i];
		} else if (a[i] < b[j]) {
			if (i == upper)
				return b[j];
			return get(a, b, k, i, (i + 1 + upper) / 2, upper);
		} else { // a[i] > b[j]
			if (i == lower)
				return a[i];
			if (i == lower + 1)
				return a[lower] >= b[j + 1] ? a[lower] : Math.min(a[i],
						b[j + 1]);
			return get(a, b, k, lower, (i - 1 + lower) / 2, i);
		}
	}*/
	
	/**
	 * Cleaner logic
	 */
	public int find(int[] a, int[] b, int k) {
		int[] s = a.length >= b.length? b : a;
		int[] l = a.length >= b.length? a : b;
		
		int lower = Math.max(0, k - l.length - 1);
		int upper = Math.min(s.length - 1, k - 1);
		
		return find(s, l, k, lower, upper);
	}
	
	private int find(int[] a, int[] b, int k, int lower, int upper) {
		int i = (lower + upper) / 2;
		int j = k - i - 2;
		
		int a_i = a[i];
		int a_i1 = i+1 > upper? Integer.MAX_VALUE : a[i+1];
		int b_j = j<0? Integer.MIN_VALUE : b[j];
		int b_j1 = j+1 >= b.length? Integer.MAX_VALUE : b[j+1];
		
		if (lower > upper) return a_i > b_j? b_j1 : a_i1;
		
		if (a_i >= b_j && a_i <= b_j1) return a_i;
		if (b_j >= a_i && b_j <= a_i1) return b_j;
		
		if (a_i > b_j) return find(a, b, k, lower, i-1);
		return find(a, b, k, i+1, upper);
	}
}
